import java.util.Stack;
import java.util.*;
public class practice2 {

      public class ListNode {
        int val;
        ListNode next = null;
        public ListNode(int val) {
          this.val = val;
        }
      }

//     Top 101 实现局部的链表反转

        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         *
         * @param head ListNode类
         * @param m int整型
         * @param n int整型
         * @return ListNode类
         */
        public ListNode reverseBetween (ListNode head, int m, int n) {

            // 这道题目要求的是在指定范围内实现链表的反转
            // 先使用 指定范围 入栈、出栈 实现逆置的代码

            // 使用 栈 来实现修改逆置的操作，不会修改链表中的指向关系，只需要针对 值 进行修改即可

            // 创建出一个 栈
            Stack<Integer> stack = new Stack<>();
            ListNode temp = head;
            int i = 1;

            // 实现在指定范围内的元素进行入栈操作
            while(temp != null) {
                if(i >= m && i <= n) {
                    stack.push(temp.val);
                }
                temp = temp.next;
                i++;
            }

            // 在这里要进行一下重置操作
            temp = head;
            i = 1;

            // 实现将指定范围内的元素进行出栈后对当前链表进行重写修改
            while(temp != null) {
                if(i >= m && i <= n){
                    // 将后进先出的值进行弹出操作
                    temp.val = stack.pop();
                }
                temp = temp.next;
                i++;
            }

            // write code here
            // 这里直接将开始的头结点直接返回即可
            return head;
        }

}
